\section{Related Work and Technical Overview}\label{sec:related}
\paragraph{Dynamic networks.} As a step towards understanding the fundamental computational power in
dynamic networks, recent studies (see e.g., \cite{dynamic-survey,Kuhn-stoc,kuhn-podc,DPRS-arxiv} and the references therein) have investigated dynamic networks in which the network
topology changes arbitrarily from round to round. In the
worst-case model that was studied by Kuhn, Lynch, and
Oshman~\cite{Kuhn-stoc}, the communication links for
each round are chosen by an online adversary, and nodes  do not know
who their neighbors for the current round are before they broadcast
their messages. 
%Note that in this model (and as assumed in our paper also), only edges change and nodes
%are assumed to be fixed.  The only constraint on the adversary is
%that the network should be connected at each round.  
Unlike prior
models on dynamic networks, the model of~\cite{Kuhn-stoc} (like ours) does
not assume that the network eventually stops changing; therefore it requires
that the {\em algorithms work correctly and terminate even in networks that
change continually over time}.

The work of~\cite{AKL08} studied the {\em cover time} of  random walks in an evolving graph (cf. Section \ref{sec:model}) in an oblivious adversarial model. Recently, the work of \cite{clementi-podc12}, studies the flooding time of {\em Markovian} evolving dynamic graphs, a special class of evolving graphs.
%As mentioned in Section \ref{sec:model},  this dynamic graph model is more general than ours because there is no assumption of  stationarity in spectral properties. 
%Anisur: Can we reduce this part, as we said it earlier in model section 
%They showed that there exists an evolving graph in which a simple random walk takes exponential time to cover all the nodes (i.e. the  cover time), even under an oblivious adversary. 
%In a {\em regular} evolving graph, they show that the cover time is always polynomial, while this is not true in
%general if the graph is not regular.
% --- the cover time can be exponential.  
%However, they show that a lazy random walk (i.e., walk with self loops)  has polynomial cover time on all graphs. 
%We also use a similar strategy to
%show that our distributed random walk algorithms can work on non-regular graphs also, albeit at the cost
%of an increase in run time.
%While the work of \cite{AKL08} addressed the cover time of random walks
%on dynamic graphs, this paper is concerned with distributed algorithms for computing random walk samples fast
%with the goal towards applying it to fast distributed computation problems in dynamic networks.


\vspace{-0.07in}
\paragraph{Distributed random walks.} Our fast distributed random walk algorithms are based on previous such algorithms designed for
{\em static} networks \cite{DNP09-podc,DasSarmaNPT10}. These were the first sublinear  (in the length of the walk) time algorithms for performing random walks in graphs.  The algorithm of \cite{DasSarmaNPT10} performed a random walk of length $\ell$  in $\tilde{O}(\sqrt{\ell D})$  rounds (with high probability) on an undirected  network, where $D$ is the diameter of the network. %This improved over the previous best algorithm that ran in $\tilde{O}(\ell^{2/3}D^{1/3})$ rounds \cite{DNP09-podc}.
(Subsequently, the algorithm of \cite{DasSarmaNPT10} was shown to be almost time-optimal (up to polylogarithmic factors) in \cite{NanongkaiDP11}.)
The general high-level idea   of the above algorithm is using  a few short walks in the
beginning (executed in parallel) and then carefully concatenating these
walks together later as necessary.  
A main contribution of the present work is showing that building on the approach
of \cite{DasSarmaNPT10} yields speed up in random walk computations even in dynamic networks. However, there are some challenging
technical issues to overcome in this extension given the continuous dynamic nature (cf. Section \ref{sec:algo}). 
%Anisur: Is the sentence below not well defined? Some reviewer pointed out it. 
%In the dynamic setting, we focus on walks of length equal to the dynamic
%mixing time ($\tau$) which we show is a well-defined quantity (cf. Section \ref{mixing_time} in Appendix). 
One key  technical lemma (called the {\em Random walk visits Lemma}) that was used
to show the almost-optimal run time of $\tilde{O}(\sqrt{\ell D})$ does not directly apply to dynamic networks. 
%In other words, the above  does not imply a run time of of $\tilde{O}(\sqrt{\tau \Phi})$ for dynamic networks.
In the static setting, this lemma
gives a bound on the number of times  any node is visited in an $\ell$-length walk, for any  length that is not much larger than the cover time.  More precisely, the lemma states that w.h.p. any node $x$ is visited at most $\tilde{O}(d(x)\sqrt{\ell})$ times, in an $\ell$-length walk from any starting node ($d(x)$ is the degree of $x$).
In this paper, we show that a similar bound applies to an $\ell$-length random walk
on any $d$-regular evolving graph (cf. Lemma \ref{lem:visit-bound}).
A key ingredient in the above proof is  showing that a technical result due to Lyons \cite{Lyons}
can be made to work on an evolving graph.

Other recent work involving multiple random walks in {\em static} networks, but in 
different settings include Alon et. al.~\cite{AAKKLT}, Els{\"a}sser
et. al.~\cite{berenbrink+ceg:gossip},  and Cooper et al. \cite{frieze}.
%\vspace{-0.05in}
\paragraph{Information spreading.} The main application of our random walks algorithm is an improved algorithm for 
information spreading or gossip in dynamic networks. To the best of our knowledge, it gives the first
subquadratic, fully distributed, token forwarding algorithm in dynamic networks, partially  answering an open question raised in \cite{DPRS-arxiv}.  Information spreading is a fundamental
primitive in networks which has been extensively studied  (see e.g., \cite{DPRS-arxiv} and the references therein). Information spreading can be used to solve other problems such as
broadcasting and leader election. 
%Indeed, solving $n$-gossip (cf. Section \ref{sec:intro}), where
%the number of tokens is equal to the number of nodes in the network,
%and each node starts with exactly one token, allows any function of
%the initial states of the nodes to be computed, assuming that the
%nodes know $n$~\cite{Kuhn-stoc}.  

This  paper's focus is on {\em token-forwarding} algorithms, which do not manipulate tokens in any way other than
storing and forwarding them.  Token-forwarding algorithms are simple,
often easy to implement, and typically incur low overhead.  \cite{Kuhn-stoc} showed that under their adversarial
model, $k$-gossip can be solved by token-forwarding in $O(nk)$ rounds,
but that any deterministic online token-forwarding algorithm needs
$\Omega(n \log k)$ rounds. In \cite{DPRS-arxiv}, an almost matching lower bound of 
$\Omega(nk/\log n)$ is shown.
% rounds against an adversary that, at the start of
%each round, knows the randomness used by the algorithm in that round.
%This also implies that any deterministic online token-forwarding
%algorithm takes $\Omega(nk/\log n)$ rounds.  This  result applies even
%to centralized token-forwarding algorithms that have a global
%knowledge of the token distribution.
The above lower bound indicates that one cannot obtain efficient (i.e.,
subquadratic) token-forwarding algorithms for gossip in the
adversarial model of~\cite{Kuhn-stoc}.   This motivates considering
other weaker (and perhaps more realistic) models of dynamic networks.
%In fact, it is not clear whether one can solve the problem
%significantly faster even in an offline setting, in which the network
%can change arbitrarily each round, but the entire evolution is known
%to the algorithm in advance. 

\cite{DPRS-arxiv} presented a polynomial-time offline {\em centralized} token-forwarding algorithm that
solves the $k$-gossip problem on an $n$-node dynamic network in
$O(\min\{nk, n \sqrt{k \log n}\})$ rounds with high probability. This is the first known {\em subquadratic} time
token-forwarding algorithm but it is not distributed, and furthermore, the centralized algorithm needs
to know the complete evolution of the dynamic graph in advance. 
It was left open in \cite{DPRS-arxiv}
whether one can obtain a fully-distributed  and localized algorithm that also does not know anything
about how the network evolves.
In this paper, we resolve this open question in the affirmative. Our  algorithm  runs in  $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$ rounds with high probability.  This is significantly faster than the $O(nk)$-round
algorithm of \cite{Kuhn-stoc} as well as the above centralized algorithm of \cite{DPRS-arxiv} when $\tau$ and $\Phi$ are not too large. Note that $\Phi$ is bounded by $O(n)$  and in regular graphs $\tau$ is  $O(n^2)$ ($O(n^3)$ in general graphs) and so in general, our bounds cannot be better than $O(nk)$. 

\iffalse
Our distributed algorithm
is based on the algorithm of \cite{DPRS-arxiv} which consists of two phases. The first phase is the key one, which  consists
of sending the $k$ tokens to a set of {\em random} locations. In \cite{DPRS-arxiv}, this is implemented by a centralized  
algorithm assuming that the algorithm knows the entire sequence of graphs in advance. Here, we show that
this can be efficiently implemented in a distributed and localized fashion using our ``many" random walks algorithm (cf. Section \ref{sec:k-algo}) --- which shows how to efficiently perform many independent random walks simultaneously.
\fi

We note that  an alternative approach
based on network coding was due to
~\cite{haeupler:gossip,haeupler+k:dynamic}, which achieves an
$O(nk/\log n)$ rounds using $O(\log n)$-bit messages (which is not
significantly better than the $O(nk)$ bound using token-forwarding),
and $O(n + k)$ rounds with large message sizes (e.g., $\Theta(n\log n)$ bits).  
It thus follows that for large token and message sizes
there is a factor $\Omega(\min\{n,k\}/\log n)$ gap between
token-forwarding and network coding. We note that in our model we
allow only one token per edge per round and thus our bounds hold
regardless of the token size.
%For further references to using network
%coding for gossip and related problems, we refer to the recent works
%of
%~\cite{haeupler:gossip,haeupler+k:dynamic,avin1,avin2,deb+mc:coding,shah}
%and the references therein.

\iffalse
\paragraph{Decentralized computation of spectral properties.} The
work of \cite{mihail-topaware}  discusses spectral algorithms for
enhancing the topology awareness, e.g., by identifying and assigning
weights to critical links. However, the algorithms are centralized,
and it is mentioned that obtaining efficient decentralized
algorithms is a major open problem. Our algorithms are fully decentralized
and  based on performing random walks,
and so more amenable to dynamic and self-organizing networks.
\fi

